package 每日一题;

import publicClass.ListNode;

import java.util.ArrayList;

/**
 * 143. 重排链表
 * 中等
 * 1.3K
 * 相关企业
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * 示例 2：
 *
 *
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 *
 *
 * 提示：
 *
 * 链表的长度范围为 [1, 5 * 104]
 * 1 <= node.val <= 1000
 */
public class T143_重排链表 {

    //使用双向队列 每次从头尾各取一个节点
    public void reorderList(ListNode head) {

        //使用arraylist
        if (head==null){
            return;
        }

        ArrayList<ListNode> listNodes = new ArrayList<>();

        ListNode currNode = head;

        while (currNode!=null){
            listNodes.add(currNode);
            currNode = currNode.next;
        }

        int i= 0,j = listNodes.size()-1;

        while (i<j){

            listNodes.get(i).next = listNodes.get(j);
            listNodes.get(j).next = null;
            i++;
            if (i==j){
                break;
            }
            listNodes.get(j).next = listNodes.get(i);
            j--;
            listNodes.get(i).next = null;
        }



    }

}
